package com.study.algorithm.datastruct.tree.impl;

import com.study.algorithm.datastruct.tree.BinaryTreeTravel;
import com.study.algorithm.datastruct.tree.model.BinaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;


/**
 * 树遍历实现（针对二叉树）
 * 实现：前序遍历、中序遍历、后序遍历层次遍历
 * 针对所有遍历的非递归写法，参考层次遍历
 * 修改记录：
 * 补充前序遍历非递归方式
 * 修改层次遍历参数，使其与其他遍历参数保持一致，协调
 */

public class BinaryTreeTravelImpl implements BinaryTreeTravel {

    public static volatile BinaryTreeTravel instance;

    public static BinaryTreeTravel getInstance() {

        if (instance == null) {
            synchronized (BinaryTreeTravel.class) {
                if (instance == null) {
                    instance = new BinaryTreeTravelImpl();
                }
            }
        }
        return instance;
    }

    @Override
    public List<BinaryTree> getPreTravelTrace(BinaryTree binaryTree) {
        List<BinaryTree> traceList = new ArrayList<>();
        if (binaryTree == null) {
            return traceList;
        }
        //通过非递归方式
//        preTravelThroughNotRecusion(binaryTree, traceList);
        //通过递归方式
        traceList.add(binaryTree);
        preTrave(binaryTree.getLeftChildNode(), traceList);
        preTrave(binaryTree.getRightChildNode(), traceList);
        return traceList;
    }


    @Override
    public List<BinaryTree> getMiddleTravelTrace(BinaryTree binaryTree) {
        List<BinaryTree> traceList = new ArrayList<>();
        if (binaryTree == null) {
            return traceList;
        }

        middleTrave(binaryTree.getLeftChildNode(), traceList);
        traceList.add(binaryTree);
        middleTrave(binaryTree.getRightChildNode(), traceList);
        return traceList;
    }

    @Override
    public List<BinaryTree> getAfterTravelTrace(BinaryTree binaryTree) {
        List<BinaryTree> traceList = new ArrayList<>();
        if (binaryTree == null) {
            return traceList;
        }
        afterTrave(binaryTree.getLeftChildNode(), traceList);
        afterTrave(binaryTree.getRightChildNode(), traceList);
        traceList.add(binaryTree);
        return traceList;
    }

    @Override
    public List<BinaryTree> getLevelTravelTrace(BinaryTree binaryTree) {
        List<BinaryTree> traceList = new ArrayList<>();
        if (binaryTree == null) {
            return traceList;
        }
        levelTravel(binaryTree, traceList);
        return traceList;
    }


    /**
     * 通过非递归方式实现前序遍历
     *
     * @param binaryTree
     * @param traceList
     */
    private void preTravelThroughNotRecusion(BinaryTree binaryTree, List<Object> traceList) {
        Stack<BinaryTree> treeStack = new Stack<>();
        if (binaryTree == null) {
            return;
        }
        treeStack.push(binaryTree);
        while (!treeStack.empty()) {
            BinaryTree tempNode = treeStack.pop();
            if (tempNode == null) {
                continue;
            }
            traceList.add(tempNode.getWeight());
            //下面两个if语句内容不能互换，这是根据入栈出栈规律得出的入栈方式
            if (tempNode.hasRightChildNode()) {
                treeStack.push(tempNode.getRightChildNode());
            }
            if (tempNode.hasLeftChildNode()) {
                treeStack.push(tempNode.getLeftChildNode());
            }
        }
    }


    private void levelTravel(BinaryTree binaryTree, List<BinaryTree> traceList) {
        Queue<BinaryTree> treeQueue = new LinkedBlockingQueue<>();
        treeQueue.add(binaryTree);
        while (!treeQueue.isEmpty()) {
            BinaryTree nextBinaryTree = treeQueue.poll();
            if (nextBinaryTree == null) {
                continue;
            }
            traceList.add(nextBinaryTree);
            if (nextBinaryTree.hasLeftChildNode()) {
                treeQueue.add(nextBinaryTree.getLeftChildNode());
            }
            if (nextBinaryTree.hasRightChildNode()) {
                treeQueue.add(nextBinaryTree.getRightChildNode());
            }
        }
    }


    private void preTrave(BinaryTree binaryTree, List<BinaryTree> traceList) {
        if (binaryTree == null) {
            return;
        }
        traceList.add(binaryTree);
        preTrave(binaryTree.getLeftChildNode(), traceList);
        preTrave(binaryTree.getRightChildNode(), traceList);
    }


    private void middleTrave(BinaryTree binaryTree, List<BinaryTree> traceList) {
        if (binaryTree == null) {
            return;
        }
        middleTrave(binaryTree.getLeftChildNode(), traceList);
        traceList.add(binaryTree);
        middleTrave(binaryTree.getRightChildNode(), traceList);
    }

    private void afterTrave(BinaryTree binaryTree, List<BinaryTree> traceList) {
        if (binaryTree == null) {
            return;
        }
        afterTrave(binaryTree.getLeftChildNode(), traceList);
        afterTrave(binaryTree.getRightChildNode(), traceList);
        traceList.add(binaryTree);
    }
}
